In today's age of communications, the use of cryptography is becoming increasingly important to protect confidential communications between a sender and a receiver transmitted over public or easily accessible communications channels such as telephone lines, satellite links, wireless networks, cellular phone systems, etc. The basic idea of cryptography is to first scramble or encrypt the private message, and then send the encrypted message over the communications channel to the receiver where the message is then decrypted and read. If the encrypted message is intercepted by an unauthorized party and cannot be decrypted, it will be unintelligible.
In key-based encryption systems, the message to be sent is encrypted with a "key" or "communications key" which is a code known only to the sender and receiver and is not known to other unauthorized parties who may try to intercept the encrypted message. If the sender and receiver possess and agree to use the same key, the sender can encrypt the message with the communications key and send the unintelligible, encrypted message over the communications channel to the receiver, who can then decrypt the message using the same communications key used by the sender to encrypt the message.
In 1977, the United States National Bureau of Standards decided on a defined encryption algorithm known as the Data Encryption Standard (DES), which is now the standard for the encryption of certain classes of data. DES encryption is currently used by federal agencies as well as by private companies in areas such as electronic banking and money transfer. DES encryption works with a user-supplied data encryption key with a word length of 56 bits. The encryption key, which must be known by both the sender and receiver of the message, is used to encrypt the message, which then appears as an apparently random sequence of unintelligible bits. Since both the encryption and decryption procedures used with DES are publicly known, maintaining the secrecy of the encryption key is imperative when using any DES encryption system. Today there are commercially available integrated circuits which can implement the DES encryption and decryption procedure.
As with DES encryption, one of the largest problems encountered in any key-based encryption system is the need to keep the key secure. One solution is to frequently update the communications key such that even if one key is recovered by an unauthorized user, a subsequent key change will not allow decryption of subsequent messages. To this end, many different methods of key distribution have been devised.
In one widely-used method of key distribution, a human courier or "trusted friend" can be used to physically distribute new keys to the remote systems on a periodic basis. This method can be problematic, however, if the confidence of the trusted friend is compromised or the key is intercepted along the way by an unauthorized party.
Another type of key distribution system is known as a public key system in which the communications key need not be physically distributed or even agreed on in advance by the sender and receiver. In such a system, User A publishes a public encoding key E.sub.A to all users of the system and keeps private a decoding key D.sub.A, whereby D.sub.A (E.sub.A (M))=M, where M is the message to be sent, E.sub.A (M) is the encryption of message M, and D.sub.A (E.sub.A (M) is the description of encrypted message M. In such a system, however, User A must not publicly reveal D.sub.A when showing E.sub.A, and the decoding key D.sub.A must not be computable from encoding key E.sub.A. Using this system, User B, who desires to send a message to User A, can look up the encoding key E.sub.A of User A which is published. User B then uses E.sub.A to encrypt the message to be sent to User A. Upon receipt of the encrypted message, User A can quickly decode the message whereas other users or unauthorized parties who do not possess D.sub.A cannot easily ascertain the message from the published E.sub.A. This system is extremely slow, however, when used to send large messages due to its reliance on intensive computations needed to decrypt the message.
Another key distribution system, known as double encryption, is disclosed in U.S. Pat. No. 5,029,207 to Gammie. In this system, an external security module for a television signal decoder is provided in which the key to be sent is encrypted using two secret serial numbers known only to the master and the particular remote subscriber. The key used to descramble the program signal is first encrypted with the secret serial number of the remote unit's replaceable security module, and then encrypted again with the secret serial number of the remote unit's decoder. The decoder then uses its two secret serial numbers to work backwards and decrypt the key, which it then uses to descramble the program signal.
U.S. Pat. No. 5,146,498 to Smith discloses a method of remotely changing the encryption key where an original key is stored in a remote unit, and the master unit sends a signal to effectuate a key change based on operations performed on the original key. The key itself, however, is not sent, but rather the new key is generated as a result of mathematical operations on the original key initiated from a key change command sent from the master unit.
U.S. Pat. No. 4,731,840 to Mniszewski et al. discloses a method for encrypting and sending digital key data using DES encryption. Each remote unit used in the system contains a set of key-encryption keys indexed by a common system. The master unit, upon request from the remote unit, generates a key and encrypts it with a preselected key-encryption key. The encrypted key and an index designator is sent to a remote unit wherein the key is decrypted to reproduce a data encryption key.
Other systems, such as that disclosed in U.S. Pat. No. 5,159,633 to Nakamura, use combined public and secret key encryption systems. In Nakamura, storage information is encrypted with a public key system while real time transmission data such as a video signal is encrypted with a secret key system.
FIG. 1 shows another example of a prior art key encryption system that includes a central or master unit 100 and a remote unit 120. At master unit 100, a new key 102 is chosen by a random number generator (RNG) 103 to serve as the communications key and must be safely transferred to remote unit 120 over communications channel 111. To this end, master unit 100 generates and then encrypts the new key 102 with a master key 122 of remote unit 120, using DES encryption unit 104 to thereby generate encrypted key 110. Encrypted key 110 is then sent to the remote unit 120 which will then decrypt encrypted key 110 using DES encryption unit 105 and master key 122 to recover new key 102. New key 102 is then used as the new communications key for subsequent communications between master unit 100 and remote unit 120.
This system, however, is subject to attack as follows. First, the attacker intercepts and records the first message sent to remote unit 120 which contains the encrypted key 110. The attacker then records subsequent messages sent encrypted with new key 102. The attacker can then break the code on subsequent messages and recover new key 102. With new key 102 now obtained, the attacker can decrypt the first message and recover master key 122. With knowledge of master key 122, all subsequent messages are vulnerable to interception.
Other data encryption techniques are used by the cellular phone industry to protect not only communications between callers, but to protect the security of identification numbers of remote cellular phones subscribing to the particular system. However, the present systems that attempt to maintain the secrecy of the remote phone's identification number are subject to attack. Currently, when a cellular phone is used, it must first establish initial contact with the base station. When the initial contact is made, the remote cellular phone is then interrogated by the base station in order to obtain the cellular phone's identification number. This identification number is then used by the cellular phone system to invoice the customer for the call. However, attackers can intercept the initial transmission and determine the remote user's identification number, which they can then proceed to install in a cellular phone of their own which can now be used or sold. Calls made from this "imposter" phone will then be billed to the original subscriber. This type of cellular telephone fraud has swamped the phone companies with requests for new telephone numbers and for billing refunds from cellular users, resulting in the loss by the phone companies of significant amounts of money.
Accordingly, in any situation in which communication between a sender and a receiver must be kept confidential, there is a need to provide a key encryption system that is relatively easy to implement and less vulnerable to attack by unauthorized parties. There has been a long felt need to provide such an improved key encryption system which is extremely secure and nearly impossible to break and decrypt subsequent communication keys. There is also a need to provide an improved encryption system that will prevent cellular phone fraud and fraud in similar types of systems by authenticating the identity of the remote unit.